Elisa Celis
Motivated by the problem of detecting the source of an epidemic, we revisit the classic metric dimension problem. The metric dimension of a graph, introduced by Erdos and Renyi, is the minimum size subset of vertices such that all vertices in the graph are uniquely determined by the vector of distances to those in the subset. Interest in this problem arose due to its application to problems such as network verification, navigation, and image digitization, and numerous hardness and algorithmic results have been produced. In this talk I will first show how the metric dimension problem also arises naturally when one is interested in detecting the source of an epidemic. Subsequently, I will present an optimal approximation algorithm for the metric dimension problem.
This is joint work with Brunella Spinelli and Patrick Thiran.